DSC 40B – Theoretical Foundations of Data Science II
Problems tagged with "aggregate analysis"
Problem #109
Tags: aggregate analysis, breadth first search
Consider the code below, which is a modification of the code for bfs
given in lecture:
from collections import deque
def modified_full_bfs(graph):
status = {node: 'undiscovered' for node in graph.nodes}
for node in graph.nodes:
if status[node] == 'undiscovered':
modified_bfs(graph, node, status)
def modified_bfs(graph, source, status=None):
"""Start a BFS at `source`."""
if status is None:
status = {node: 'undiscovered' for node in graph.nodes}
status[source] = 'pending'
pending = deque([source])
# while there are still pending nodes
while pending:
u = pending.popleft()
for v in graph.neighbors(u):
# explore edge (u,v)
if status[v] == 'undiscovered':
status[v] = 'pending'
# append to right
pending.append(v)
for z in graph.nodes: # <----- new line!
print(z, status[z]) # <----- new line!
status[u] = 'visited'
Notice the two new lines; these lines print all node statuses any time that an undiscovered node has been found.
What is the time complexity of this modified modified_full_bfs
? State your answer in asymptotic notation in terms of the number of nodes,
Solution
First, the newly-added code (the for z in graph.nodes
loop), takes
This loop is encountered every time we add a node to the queue (except for the root node, which we add to the queue right at the beginning of BFS). Since this is a connected graph, each node will get added to the pending queue exactly once, meaning that this new code is encountered exactly
Since the new code takes
You might wonder why the time complexity isn't if
-statement before it is True
, and this will happen on only a subset of the
Problem #115
Tags: depth first search, aggregate analysis
Suppose an undirected graph
Including the root call of dfs
on node dfs
will be made?
Solution
34
Problem #126
Tags: aggregate analysis, graph representations
Suppose a graph adj_list
. What is the time complexity of the below code?
for lst in adj_list:
for u in lst:
print(u)
Solution
Problem #130
Tags: depth first search, aggregate analysis
Consider the code shown below. It shows DFS as seen in lecture, with one modification: a print
statement in the for-loop.
def dfs(graph, u, status=None):
"""Start a DFS at `u`."""
# initialize status if it was not passed
if status is None:
status = {node: 'undiscovered' for node in graph.nodes}
status[u] = 'pending'
for v in graph.neighbors(u):
print("Hello!")
if status[v] == 'undiscovered':
dfs(graph, v, status)
status[u] = 'visited'
How many times will "Hello!"
be printed if dfs
is run on the graph below using node dfs
will not be restarted if the first call does not explore the whole graph.

Solution
12
Problem #133
Tags: aggregate analysis
A ``hub and spoke'' graph with

What is the worst case time complexity of an optimal algorithm which takes as input an arbitrary graph
Solution
Next, take an arbitrary node and compute its degree (in
If the degree is not
If you see a degree that's neither 1 nor
Problem #154
Tags: aggregate analysis
Suppose the code below is run on a graph
for u in graph.nodes:
for v in graph.neighbors(u):
print(u, v)
Solution
Problem #245
Tags: aggregate analysis
Suppose a graph adj_list
. What is the time complexity of the below code?
for u, lst in enumerate(adj_list):
for v in lst:
print(u, v, "is an edge")
Solution
2nd option: